package com.example.leetcode.trainingcamp.week3.expand;

import java.util.LinkedList;

/**
 * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 *
 * <p>示例:
 *
 * <p>输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:
 *
 * <p>滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3
 * 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer59I {
    //nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

    /**
     * 暴力求解
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0){
            return new int[0];
        }
        int[] result = new int[len-k+1];
        for (int i = 0;i<=len-k;i++){
            int index = i;
            for (int j = i+1; j<i+k;j++){
                if (nums[index] <nums[j]){
                    index = j;
                }
            }
            result[i] = nums[index];
        }
        return result;
    }
   // //nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

    /**
     * 单调栈
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums,int k){
        int len = nums.length;
        if (len == 0){
            return new int[0];
        }
        LinkedList<Integer> stack = new LinkedList<>();
        // 处理第一个节点
        for (int i =0 ;i<k;i++){
            while (!stack.isEmpty() && nums[i] > nums[stack.peekLast()]){
                stack.pollLast();
            }
            stack.offerLast(i);
        }
        int[] result = new int[len-k+1];
        result[0] = nums[stack.peekFirst()];
        for (int i =k;i<len;i++){
            while (!stack.isEmpty() && nums[i] > nums[stack.peekLast()]){
                stack.pollLast();
            }
            stack.offerLast(i);
            // 例如 result[4] = 的值 只能在 i = 4 ~ 6 之间产生 假设数组递减的，那么栈就是一直加元素，递减，所以需要将前面的元素去除
            while (stack.peekFirst()<= i- k){
                stack.pollFirst();
            }
            result[i-k+1] = nums[stack.peekFirst()];
        }
        return result;
    }
}


class TestOffer59I{
  public static void main(String[] args) {
    Offer59I o = new Offer59I();
    int[] nums = {1,3,-1,-3,5,3,6,7};
    int[] ints = o.maxSlidingWindow2(nums, 3);
    for ( int i: ints) {
      System.out.println(i);
    }
  }
}